1. 题目

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 说明：

所有输入均为小写字母。 不考虑答案输出的顺序。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/group-anagrams 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

关键在于判断两个字符串是否相等，忽略字母相对位置。

可以利用哈希，这里可以选取哈希的方式为：$H(S) = \sum\limits_{i=1}^{26}num[i]*i*B^{26-i}$

其中，$num[i]$为小写字母ch的个数（ch-'a'+1）

3. 代码

#define ull unsigned long long
const ull B = 1e9+7;
vector<int> num(27);
class Solution {
public:
    ull getHash(string str){
        ull ans = 0;
        fill(num.begin(), num.end(), 0);
        for(auto &x:str)  
            num[x-'a'+1]++;
        for(int i=1;i<=26;++i)
            ans = ans*B + num[i]*i;
        return ans;
    }
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<ull,int> record;
        vector<vector<string>> res;
        int len = strs.size();
        for(int i=0; i<len; ++i){
            ull hashValue = getHash(strs[i]);
            if(!record.count(hashValue)){
                vector<string> empt;
                res.push_back(empt);
                record.emplace(hashValue, record.size());
            }     
            res[record[hashValue]].push_back(strs[i]);         
        }
        return res;
    }
};